|
In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph〔〔.〕) is a graph with vertices in which every subgraph of vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex. ==Examples== Any odd-length cycle graph is factor-critical,〔 as is any complete graph with an odd number of vertices.〔 More generally, every Hamiltonian graph with an odd number of vertices is factor-critical. The friendship graphs (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but not Hamiltonian. If a graph is factor-critical, then so is the Mycielskian of . For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical.〔.〕 Every 2-vertex-connected claw-free graph with an odd number of vertices is factor-critical. For instance, the 11-vertex graph formed by removing a vertex from the regular icosahedron (the graph of the gyroelongated pentagonal pyramid) is both 2-connected and claw-free, so it is factor-critical. This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Factor-critical graph」の詳細全文を読む スポンサード リンク
|